%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graphbook/
%%
%% Copyright (C) 2009--2013 Minh Van Nguyen <mvngu.name@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{algorithmic}[1]
%% input
\Require A connected weighted graph $G = (V,E)$ with weight function $w$.
\Ensure A minimum spanning tree of $G$.
%%
%% algorithm body
\State $m \gets |V|$
\State $T \gets \emptyset$
\State sort $E = \{e_1, e_2, \dots, e_n\}$ by weights so that $w(e_1) \leq w(w_2) \leq \cdots \leq w(e_n)$
\For{$i \gets 1, 2, \dots, n$}
  \If{\rm $e_i \notin E(T)$ and $T \cup \{e_i\}$ is acyclic\label{alg:Kruskal:edge_not_in_T_acyclic}}
    \State $T \gets T \cup \{e_i\}$
  \EndIf
  \If{$|T| = m - 1$}
    \State \Return $T$
  \EndIf
\EndFor
\end{algorithmic}
